In computer graphics, various methods have been developed for rendering a three-dimensional scene. One rendering method is ray tracing. Ray tracing is a global illumination rendering method that is able to render advanced visual effects such as reflection, refraction, and shadows. Ray tracing works by modeling and tracing the paths of individual rays of light as those rays make contact with three-dimensional objects within a scene. Ray tracing is thus capable of rendering a more realistic view of a scene than other rendering methods which are incapable of modeling reflection, refraction, and shadows.
In ray tracing, the objects in a three-dimensional scene are generally modeled as geometric primitives. A geometric primitive can either be a point, a line, a two-dimensional shape, or a three-dimensional shape. For example, one commonly used geometric primitive is a triangle, and the objects in a three-dimensional scene can be modeled as thousands or millions of triangles. Given a three-dimensional scene modeled as thousands or millions of geometric primitives, the main objective of ray tracing is to determine how a given number or rays intersect with the geometric primitives in the scene. Because of the high number of geometric primitive in even relatively basic three-dimensional scenes, simply checking each ray against each geometric primitive is very inefficient. Often ray tracing methods reduce the number of these intersection checks by using a hierarchical data structure.
Hierarchical data structures enable ray tracing methods to perform a relatively low-cost check to determine if a ray is in the general vicinity of a geometric primitive before having to perform a relatively high-cost check to determine if the ray intersects with the geometric primitive. In the event that the relatively low-cost check determines that the ray is not in the general vicinity of the geometric primitive, the relatively high-cost check can be avoided altogether, thus resulting in a lower overall cost of ray tracing a scene.
For example, a three-dimensional scene can be spatially partitioned into a hierarchical data structure having parent nodes and child nodes. Such a structure can be hierarchical in the sense that each child node is spatially bounded within its parent. Each parent can have one or more child nodes, and each geometric primitive can correspond to exactly one child node, although each child node may bound multiple geometric primitives.
Using this example hierarchical data structure, where a child node includes two geometric primitives, a ray tracing method can first perform a relatively low-cost check for an intersection between a ray and the child node. Where the ray does not intersect the child node, the ray tracing method can avoid a relatively high-cost check for an intersection between the ray and the two geometric primitives bounded by the node, since it is known that where the ray does not intersect with a node the ray will also not intersect with any child nodes or geometric primitives bounded within the node. In this way, the numbers of intersection checks can be lowered.
Unfortunately, however, even using the a hierarchical data structure, such as the example hierarchical data structure disclosed above, a typical ray tracing method may nevertheless remain very costly in terms of time and processing resources, due in part to a large number of rays that must be traced through a three-dimensional scene. For example, if the final desired pixel resolution for a three-dimensional scene is 800×600, some ray tracing methods would initially assign one ray to each pixel, resulting in 480,000 rays that must be traced through the scene. The number of node and geometric intersection tests required to ray trace each of the 480,000 rays to successfully render the scene can make rendering the scene using ray tracing very costly in terms of time and processing resources compared to other rendering methods such as Z-buffering. The time it takes to ray trace a scene can be excessively slow to make ray tracing a viable alternative to other rendering methods, such as Z-buffering, especially for applications that make use of dynamically changing scenes, such as simulation and game applications.